//Design a data structure that follows the constraints of a Least Recently Used 
//(LRU) cache. 
//
// Implement the LRUCache class: 
//
// 
// LRUCache(int capacity) Initialize the LRU cache with positive size capacity. 
//
// int get(int key) Return the value of the key if the key exists, otherwise ret
//urn -1. 
// void put(int key, int value) Update the value of the key if the key exists. O
//therwise, add the key-value pair to the cache. If the number of keys exceeds the
// capacity from this operation, evict the least recently used key. 
// 
//
// The functions get and put must each run in O(1) average time complexity. 
//
// 
// Example 1: 
//
// 
//Input
//["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
//[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
//Output
//[null, null, null, 1, null, -1, null, -1, 3, 4]
//
//Explanation
//LRUCache lRUCache = new LRUCache(2);
//lRUCache.put(1, 1); // cache is {1=1}
//lRUCache.put(2, 2); // cache is {1=1, 2=2}
//lRUCache.get(1);    // return 1
//lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
//lRUCache.get(2);    // returns -1 (not found)
//lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
//lRUCache.get(1);    // return -1 (not found)
//lRUCache.get(3);    // return 3
//lRUCache.get(4);    // return 4
// 
//
// 
// Constraints: 
//
// 
// 1 <= capacity <= 3000 
// 0 <= key <= 104 
// 0 <= value <= 105 
// At most 2 * 105 calls will be made to get and put. 
// 
// Related Topics 设计 
// 👍 1448 👎 0

package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

class P146LruCache {
    public static void main(String[] args) {
        LRUCache lruCache = new P146LruCache().new LRUCache(2);
        lruCache.put(2, 1);
        lruCache.put(2, 2);
        System.out.println(lruCache.get(2));
        lruCache.put(1, 1);
        lruCache.put(4, 1);
        System.out.println(lruCache.get(2));

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class LRUCache {
        class Node {
            Node pre;
            Node next;
            int val;
            int key;

            public Node(int key, int val) {
                this.key = key;
                this.val = val;
            }

            public Node getPre() {
                return pre;
            }

            public void setPre(Node pre) {
                this.pre = pre;
            }

            public Node getNext() {
                return next;
            }

            public void setNext(Node next) {
                this.next = next;
            }

            public int getVal() {
                return val;
            }

            public void setVal(int val) {
                this.val = val;
            }
        }

        Map<Integer, Node> map = new HashMap<>();
        ;
        Node head;
        Node tail;
        int capacity;

        public void moveToHead(Node node) {
            if (head != node) {
                if (head == null) {
                    head = node;
                    tail = node;
                } else {
                    if (tail == node) {
                        tail = node.pre;
                        tail.next = null;
                    } else {
                        Node next = node.next;
                        Node pre = node.pre;
                        if (next != null && pre != null) {
                            pre.next = next;
                            next.pre = pre;
                        }
                    }
                    node.next = head;
                    node.pre = null;
                    head.pre = node;
                    head = node;
                }
            }
        }

        public LRUCache(int capacity) {
            this.capacity = capacity;
        }

        public int get(int key) {
            if (map.containsKey(key)) {
                moveToHead(map.get(key));
                return map.get(key).val;
            }
            return -1;
        }

        public void put(int key, int value) {
            if (map.containsKey(key)) {
                Node existNode = map.get(key);
                existNode.val = value;
                moveToHead(existNode);
            } else if (map.size() < capacity) {
                Node node = new Node(key,value);
                map.put(key, node);
                moveToHead(node);
            } else {
                map.remove(tail.key);
                Node pre = tail.pre;
                if (tail.pre == null) {
                    tail = null;
                    head = null;
                }else{
                    tail.pre = null;
                    pre.next = null;
                    tail = pre;
                }

                Node node = new Node(key,value);
                map.put(key, node);
                moveToHead(node);
            }
        }
    }

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
//leetcode submit region end(Prohibit modification and deletion)

}